Geometric median

For another use of the term median in geometry, see Median (geometry).

The geometric median of a discrete set of sample points in a Euclidean space is the point minimizing the sum of distances to the sample points. This generalizes the median, which has the property of minimizing the sum of distances for one-dimensional data, and provides a central tendency in higher dimensions. It is also known as the Fermat–Weber point or 1-median.[1]

The geometric median is an important estimator of location in statistics. It is also a standard problem in facility location, where it models the problem of locating a facility to minimize the cost of transportation.

The special case of the problem for three points in the plane (that is, m = 3 and n = 2) is sometimes also known as Fermat's problem; it arises in the construction of minimal Steiner trees, and was originally posed as a problem by Pierre de Fermat to Evangelista Torricelli, who solved it. Its solution is now known as the Fermat point of the triangle formed by the three sample points. Alfred Weber's name is associated with the more general Fermat–Weber problem due to a discussion of the problem in his 1909 book on facility location.

Wesolowsky (1993) provides a survey of the problem. See Fekete, Mitchell, and Beurer (2003) for generalizations of the problem to non-discrete point sets.

Contents

Definition

Formally, for a given set of m points x_1, x_2, \dots, x_m\, with each x_i \in \mathbb{R}^n, the geometric median is defined as

Geometric Median =\underset{y \in \mathbb{R}^n}{\operatorname{arg\,min}} \sum_{i=1}^m \left \| x_i-y \right \|_2

Note that argmin means the value of the argument y which minimizes the sum. In this case, it is the point y from where the sum of all Euclidean distances to the x_i's is minimum.

Properties

Special cases

Computation

Despite being an easy to understand concept, computing the geometric median poses a challenge. The centroid or center of mass, defined similarly to the geometric median as minimizing the sum of the squares of the distances to each sample, can be found by a simple formula — its coordinates are the averages of the coordinates of the samples — but no such formula is known for the geometric median, and it has been shown that no explicit formula, nor an exact algorithm involving only arithmetic operations and kth roots can exist in general. Therefore only numerical or symbolic approximations to the solution of this problem are possible under this model of computation.[3]

However, it is straightforward to calculate an approximation to the geometric median using an iterative procedure in which each step produces a more accurate approximation. Procedures of this type can be derived from the fact that the sum of distances is a convex function, since the distance to each sample point is convex and the sum of convex functions remains convex. Therefore, procedures that decrease the sum of distances at each step cannot get trapped in a local optimum.

One common approach of this type, called Weiszfeld's algorithm,[4] is a form of iteratively re-weighted least squares. This algorithm defines a set of weights that are inversely proportional to the distances from the current estimate to the samples, and creates a new estimate that is the weighted average of the samples according to these weights. That is,

\left. y_{i%2B1}=\left( \sum_{j=1}^m \frac{x_j}{\| x_j - y_i \|} \right) \right/ \left( \sum_{j=1}^m \frac{1}{\| x_j - y_i \|} \right).

Bose et al. (2003) describe more sophisticated geometric optimization procedures for finding approximately optimal solutions to this problem. As Nie, Parrilo & Sturmfels (2008) show, the problem can also be represented as a semidefinite program.

Implicit formula

If y is distinct from all the given points, xj, then y is the geometric median if and only if it satisfies:

0 = \sum_{j=1}^m \frac {x_j - y} {\left \| x_j - y \right \|}.

This is equivalent to:

\left. y = \left( \sum_{j=1}^m \frac{x_j}{\| x_j - y \|} \right) \right/ \left( \sum_{j=1}^m \frac{1}{\| x_j - y \|} \right)

which is closely related to Weiszfeld's algorithm.

If y is equal to some of the given points, then y is the geometric median if and only if there are vectors uj such that:

0 = \sum_{j=1}^m u_j

where for xj ≠ y,

u_j = \frac {x_j - y} {\left \| x_j - y \right \|}

and for xj = y,

\| u_j \| \leq 1 .

Generalizations

The geometric median can be generalized from Euclidean spaces to general Riemannian manifolds (and even metric spaces) using the same idea which is used to define the Fréchet mean on a Riemannian manifold. Let M be a Riemannian manifold with corresponding distance function d(\cdot, \cdot), let w_1, \ldots, w_n be n weights summing to 1, and let x_1, \ldots, x_n be n observations from M. Then we define the weighted geometric median m (or weighted Fréchet median) of the data points as

m = \underset{x \in M}{\operatorname{arg\,min}} \sum_{i=1}^n w_i d(x,x_i) .

If all the weights are equal, we say simply that m is the geometric median.

See also

Notes

  1. ^ The more general k-median problem asks for the location of k cluster centers minimizing the sum of distances from each sample point to its nearest center.
  2. ^ Lopuhaä and Rousseeuw (1991).
  3. ^ Bajaj (1986), Bajaj (1988). Earlier, Cockayne and Melzak (1969) proved that the Steiner point for 5 points in the plane cannot be constructed with ruler and compass
  4. ^ Weiszfeld (1937); Kuhn (1973); Chandrasekaran and Tamir (1989).

References